package leetcode51_60;

import org.junit.Test;

import java.util.Arrays;
import java.util.List;

/**
 * @author shhjiang_001
 * @create 2020-06-18 19:42
 */

        /*
        给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
        示例:
        输入: [-2,1,-3,4,-1,2,1,-5,4],
        输出: 6
        解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
        */

public class Solution53 {

    // 动态规划
    public int maxSubArray1(int[] nums) {
       int res = 0;
        for (int i = 1; i <nums.length ; i++) {
            if (nums[i-1]>0){
                nums[i] = nums[i]+nums[i-1];
            }
        }
        Arrays.sort(nums);
        res = nums[nums.length-1];
       return res ;

    }

    // 贪心算法
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        int temp = 0;
        for (int i = 0; i < nums.length ; i++) {
            temp = temp+nums[i];
            res = Math.max(res,temp);
            if (temp < 0){
                temp = 0;
            }
        }
        return res;
    }
    @Test
    public void test(){
        maxSubArray(new int[]{8,-19,5,-4,20});
    }
}
